package org.dlsu.mt.parser.generator;

import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.Enumeration;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.StringTokenizer;
import java.util.Vector;

/**
 * The parse table class is a representation of your parse table. This allows parse table allows multiple
 * entries to be associated with a state-symbol pair. Calling the parse table's saveToFile() method saves
 * the parsing table in a text file and can also be loaded back to a class using the loadFromFile() method.
 * The parse table can be generator from an input grammar using GLRParserGenerator.
 */

public class ParseTable {
	/**
	 * The table representation as a 2-dimensional array of vector.
	 * The first dimension represents the state and the second as the symbol
	 * For every state-symbol pair is a vector of parse table entries
	 */
	protected Vector[][] table;
	/**
	 * The set of terminals supported by the table
	 */
	protected HashSet terminals;
	/**
	 * The set of non-terminals supported by the table
	 */
	protected HashSet nonterminals;
	/**
	 * The integer mapping of each symbol to the table
	 */
	protected Hashtable tableMapping;
	/**
	 * The grammar as a list of rules/production that is represented by the table
	 */
	protected Vector rules;
	/**
	 * The total number of states inside the table
	 */
	protected int statesCount;
	/**
	 * The start symbol for the grammar
	 */
	protected String startSymbol;
	/**
	 * The initial state of the grammar
	 */
	protected int initialState;
	private Vector orderedTableMap = new Vector(); // Chronological ordering of the symbols based on their integer mappings
	/**
	 * The marker for the end of the string
	 */
	public static final String ENDMARKER = "$";
	/**
	 * The supported empty symbol
	 */
	public static final String EMPTY = "**EMPTY**";

	/**
	 * Creates a parse table
	 *
	 * @param terminals The set of terminals
	 * @param nonterminals The set of non-terminals
	 * @param rules The list rules/productions of the grammar
	 * @param statesCount the number of state that the table has
	 *@param startSymbol The start symbol for the grammar
	 */
	public ParseTable(HashSet terminals, HashSet nonterminals, Vector rules, int statesCount, String startSymbol, int initialState) {
		String symbol;
		Iterator iterator;
		this.statesCount = statesCount;
		this.startSymbol = startSymbol;
		this.initialState = initialState;

		this.terminals = terminals;
		this.nonterminals = nonterminals;
		this.rules = rules;

		initTableMapping();
	}

	private ParseTable() {
		terminals = new HashSet();
		nonterminals = new HashSet();
		rules = new Vector();
	}

	/**
	 * Initializes and fill up the tableMapping Hashtable, orderedTableMap and table
	 */
	private void initTableMapping() {
		String symbol;
		Iterator iterator;
		int terminalsCount,nonterminalsCount;
		int counter=0;

		terminalsCount=terminals.size();
		nonterminalsCount=nonterminals.size();

		tableMapping = new Hashtable(terminalsCount+nonterminalsCount);
		iterator = terminals.iterator();
		while(iterator.hasNext()) {
			symbol = (String) iterator.next();
			orderedTableMap.add(symbol.toUpperCase());
			tableMapping.put( symbol.toUpperCase(), new Integer(counter++));
		}
		iterator = nonterminals.iterator();
		while(iterator.hasNext()) {
			symbol = (String) iterator.next();
			orderedTableMap.add(symbol.toUpperCase());
			tableMapping.put( symbol.toUpperCase(), new Integer(counter++));
		}

		table = new Vector[statesCount][terminalsCount+nonterminalsCount];
		for(int i=0;i<statesCount;i++)
			for(int j=0;j<terminalsCount+nonterminalsCount;j++)
				table[i][j] = new Vector(1);
	}

	/**
	 * Gets the entries inside a table
	 *
	 * @param state The state where the particular table entry
	 * @param symbol The symbol where the particular table entry
	 * @return The vector or list of parse table entries stored in a state and symbol pair
	 */
	public Vector getEntry(int state, String symbol) throws RuntimeException {
		Integer i;
		if(statesCount <= state || state < 0)
			throw new RuntimeException("Invalid state:"+state);
		if( (i = (Integer) tableMapping.get(symbol.toUpperCase())) != null)
			return table[state][i.intValue()];
		else {
			Enumeration e =	tableMapping.keys();
			System.out.println("Table entries are: ");
			while(e.hasMoreElements())
				System.out.println(e.nextElement());
			throw new RuntimeException("Cannot find this symbol:"+ symbol);
		}
	}

	/**
	 * Adds the parse table entry to the target state and symbol
	 *
	 * @param state The state where the entry will be placed
	 * @param symbol The corresponding symbol where the entry will be placed
	 * @param pe The parse table entry to add in the table corresponding the given state, symbol
	 */
	public void addEntry(int state, String symbol, ParseTableEntry pe) throws RuntimeException {
		Integer i;
		if(statesCount <= state || state < 0)
			throw new RuntimeException("Invalid state:"+state);
		if( (i = (Integer) tableMapping.get(symbol.toUpperCase())) != null)
			table[state][i.intValue()].add(pe);
		else
			throw new RuntimeException("Cannot find this symbol:"+ symbol);
	}

	/**
	 * Gets the start symbol
	 *
	 * @return The start symbol of the parse table
	 */
	public String getStartSymbol() {
		return startSymbol;
	}

	/**
	 * Determines if the terminal string passed exists in the terminal list
	 *
     * @param s The terminal string
     * @return True if the terminal exists, false otherwise
     */
	public boolean hasTerminal(String s) {
		return terminals.contains(s.toUpperCase());
	}

	/**
	 * Determines if the non-terminal string exists in the non-terminal list
	 *
	 * @param s Non-terminal string
	 * @return True if the non-terminal exists, false otherwise
	 */
	public boolean hasNonTerminal(String s) {
		return nonterminals.contains(s.toUpperCase());
	}

	/**
	 * Gets a clone of the vector rules used by the parse table
	 *
	 * @return The list or vector of rules
	 */
	public Vector getRules(){
		return (Vector) rules.clone();
	}

	/**
	 * Gets the number of states inside the parse table
	 *
	 * @return The total number of states
	 */
	public int getStateCount() {
		return statesCount;
	}

	/**
	 * Gets a clone of the set of terminals used by the parse table
	 *
	 * @return The set of terminals
	 */
	public HashSet getTerminals() {
		return (HashSet) terminals.clone();
	}

	/**
	 * Gets a clone of the set of non-terminals used by the parse table
	 *
	 * @return The set of non-terminals
	 */
	public HashSet getNonTerminals() {
		return (HashSet) nonterminals.clone();
	}

	/**
	 * Returns the string representation of the parse table as:
	 *		<hr>
	 *		Terminals:
	 *		<terminal 1>
	 *		<terminal 2>
	 *		...
	 *		<terminal n>
	 *		NonTerminals
	 *		<non-terminal 1>
	 *		<non-terminal 2>
	 *		...
	 *		<non-terminal n>
	 *		Start:
	 *		<start symbol>
	 *		Rules:
	 *		<rule 1>
	 *		<rule 2>
	 *		...
	 *		<rule n>
	 *		**END**
	 *		<State Count>
	 *		<symbol 1>,<symbol 2>,<symbol 3>,...,<symbol n>
	 *		[<entry11a>,<entry11b>...<entry11z>];[<entry12a>,<entry12b>...<entry12z>];...[<entry1Xa>,<entry1Xb>...<entry1Xz>]
	 *		[<entry21a>,<entry21b>...<entry21z>];[<entry22a>,<entry22b>...<entry22z>];...[<entry2Xa>,<entry2Xb>...<entry2Xz>]
	 *		...
	 *		[<entryY1a>,<entryY1b>...<entryY1z>];[<entryY2a>,<entryY2b>...<entryY2z>];...[<entryYXa>,<entryYXb>...<entryYXz>]
	 *		<hr>
	 *		where X = Total number of symbols, Y = Total number of states
	 *
	 * @return The string representation of the Parse table
	 */
	public String toString() {
		StringBuffer sb = new StringBuffer();
		int i,j,k;
		Iterator iter;
		// Do not include end marker in the list of terminals
		terminals.remove(ENDMARKER);
		sb.append("Terminals:\n");
		iter = terminals.iterator();
		while(iter.hasNext())
			sb.append(iter.next()+"\n");
		// Put back the end marker
		terminals.add(ENDMARKER);

		sb.append("NonTerminals:\n");
		iter = nonterminals.iterator();
		while(iter.hasNext())
			sb.append(iter.next()+"\n");
		sb.append("Start:\n"+startSymbol+"\n");
		sb.append("Rules:\n");
		for(i=0;i<rules.size();i++)
			sb.append( ((Rule) rules.elementAt(i)).toStringNoDot()+"\n");
		sb.append("**END**\n"+statesCount+"\n");

		for(i=0;i<orderedTableMap.size()-1;i++)
			sb.append(orderedTableMap.elementAt(i)+";");
		sb.append(orderedTableMap.elementAt(i)+"\n");

		for(i=0;i<table.length;i++) {
			for(j=0;j<table[i].length;j++) {
				sb.append("[");
				for(k=0;k<table[i][j].size()-1;k++)
					sb.append(entryToString((ParseTableEntry) table[i][j].elementAt(k))+",");
				sb.append(entryToString((ParseTableEntry) table[i][j].elementAt(k)));
				sb.append("]");
				if (j+1!=table[i].length)
					sb.append(";");
			}
			sb.append("\n");
		}

		return sb.toString();
	}

	/**
	 * Rewrite the "reduce" string representation of the parse table entry p to
	 * reduce:<i>
	 * where i is the position of the rule in rules list/vector.
	 *
	 * @return The revised string representation for the parse table entry
	 */

	private String entryToString(ParseTableEntry p) {
		int i;
		if (p.getAction().equalsIgnoreCase("reduce")) {
			for(i=0;i<rules.size();i++)
				if (p.getRule().equalsNoDot(rules.elementAt(i)))
					return "reduce:"+i;
		}
		else
			return p.toString();
		return "reduction rule not found";
	}

	/**
	 * Saves the current ParseTable to a text file
	 *
	 * @param filename Text-file name to save the parse table
	 */
	public void saveToFile(String filename) throws Exception {
		PrintWriter pw = new PrintWriter(new FileOutputStream(filename));
		pw.println(toString());
		pw.close();
	}

	/**
	 * Loads a parse table from a file
	 *
	 * @param filename Text-file name to save the parse table
	 * @return ParseTable object loaded from the file
	 */
	public static ParseTable loadFromFile(String filename) throws Exception {
		GLRParserGenerator reader = new GLRParserGenerator(filename);
		ParseTable pt = new ParseTable();
		String line;
		loadSymbolsAndRules(pt, reader);
		pt.statesCount = Integer.parseInt(reader.nextLine());
		pt.initTableMapping();
		loadTableMapping(pt, reader);
		loadTableEntries(pt, reader);
		pt.initialState = 0;
		reader.closeInput();
		return pt;
	}

	/**
	 * Reloads the table mapping from a file.
	 *
	 * @param pt The parse table
	 * @param reader the file reader or handler as GLRParserGenerator
	 */
	private static void loadTableMapping(ParseTable pt, GLRParserGenerator reader) throws Exception {
		StringTokenizer st = new StringTokenizer(reader.nextLine(),";");
		String symbol;
		int ctr=0;

		pt.tableMapping = new Hashtable(pt.terminals.size()+pt.nonterminals.size());
		pt.table = new Vector[pt.statesCount][pt.terminals.size()+pt.nonterminals.size()];

		while(st.hasMoreTokens()) {
			symbol = st.nextToken().trim().toUpperCase();
			pt.orderedTableMap.add(symbol);
			pt.tableMapping.put(symbol, new Integer(ctr++));
		}
	}

	/**
	 * Reads and reloads the table entries from the text file
	 */
	private static void loadTableEntries(ParseTable pt, GLRParserGenerator reader) throws Exception {
		int i,j,k;
		StringTokenizer entryTokenizer;
		StringTokenizer valuesTokenizer, detailTokenizer;
		String action, line;

		for(i=0;i<pt.statesCount;i++) {
			j=0;
			entryTokenizer = new StringTokenizer(reader.nextLine(), ";");
			while(entryTokenizer.hasMoreTokens()) {
				pt.table[i][j] = new Vector();
				valuesTokenizer = new StringTokenizer(entryTokenizer.nextToken(),",");
				while(valuesTokenizer.hasMoreTokens()){
					detailTokenizer = new StringTokenizer(valuesTokenizer.nextToken(),"[:]");
					action = detailTokenizer.nextToken();
					if (action.equalsIgnoreCase("accept") || action.equalsIgnoreCase("error") )
						pt.table[i][j].add(new ParseTableEntry(action,-1,null));
					else if (action.equalsIgnoreCase("shift") || action.equalsIgnoreCase("goto"))
						pt.table[i][j].add(new ParseTableEntry(action, Integer.parseInt(detailTokenizer.nextToken()), null));
					else if (action.equalsIgnoreCase("reduce"))
						pt.table[i][j].add(new ParseTableEntry(action, -1, (Rule) pt.rules.elementAt(Integer.parseInt(detailTokenizer.nextToken()))));
				}
				j++;
			}
		}
	}

	/**
	 * Reads from the text file and fill up the table terminals, non-terminals, rule
	 */
	private static void loadSymbolsAndRules(ParseTable pt, GLRParserGenerator reader) throws Exception{
		String s, term, feature;
		boolean prevTerm=false;
		Rule r=null;
// Looks for keyword 'Terminals:'
		while(!(s=reader.nextToken()).equalsIgnoreCase("Terminals:"));
// Initializes list of terminals
		while(!(s=reader.nextToken()).equalsIgnoreCase("NonTerminals:")){
			if( !reader.isDelim( (s).charAt(0) ) ) {
				pt.terminals.add(s.trim().toUpperCase());
			}
		}

// Initializes list of non-terminals
		while(!(s=reader.nextToken()).equalsIgnoreCase("Start:")) {
			if( s.length()>0)
				if (!reader.isDelim(s.charAt(0))) {
					pt.nonterminals.add(s.trim().toUpperCase());
				}
		}
// Initializes start symbol
		while(!(s=reader.nextToken()).equalsIgnoreCase("Rules:")) {
			if( s.length()>0)
				if (!reader.isDelim(s.charAt(0)))
					pt.nonterminals.add( (pt.startSymbol=s.trim().toUpperCase()) );
		}
// Initializes list of rules
		while(!(s=reader.nextToken()).equalsIgnoreCase("**END**")){
			if( s.length()>0) {
				if (!reader.isDelim(s.charAt(0))) {
					if ( !pt.hasNonTerminal(s.trim()) )
						throw new RuntimeException("Symbol is not defined as a Non-Terminal: " + s);
					pt.rules.add( (r=new Rule(s)) );
					while( !(s=reader.nextToken()).equals("=") );
					while( !(s=reader.nextToken()).equals("\n")) {
						if( s.length()>0) {
							if (!reader.isDelim(s.charAt(0)))
								if(s.startsWith("*[")) {
									if (!prevTerm)
										throw new RuntimeException("Grammar rules is not for LFG: " + r.toString() + " " +s);
									else
										r.addRHSFeature(s.substring(2,s.length()-2));
									prevTerm = false;
								} else if ( pt.hasTerminal(s) || pt.hasNonTerminal(s) || s.equalsIgnoreCase(EMPTY)){
									if (prevTerm)
										r.addRHSFeature("");
									r.addRHSTerm(s);
									prevTerm = true;
								} else {
									throw new RuntimeException("Symbol is not defined: " + s);
								}
						}
					}

					if (r.getRHSTermSize() > r.getFeatureSize())
						r.addRHSFeature("");
					prevTerm=false;
				}
			}
		}
// Add the empty symbol as a nullable symbol
		pt.terminals.add(ENDMARKER);
// Skip one emtpy line
		reader.nextLine();
	}
}